package leetcode;

/**
 * @param
 * @author oyz
 * @version 1.0
 * @description: 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n))
 */
public class Code4 {




    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length>nums2.length){
            int temp[] = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;

        //分割线左边的元素个数为
        int totalNums = (m+n+1)/2;
        int left = 0;
        int right = m;
        while(left<right) {
            // 只要找到第一个数组的分割线
            int i =  left + (right - left+1)/2;
            int j = totalNums - i;
            if (nums1[i-1]>nums2[j]){
                // 说明分割线往右移动的比较多了,下一轮区间为[i+1,right]
                right = i-1;
            }else{
                // 说明分割线往右移动的比较少了,下一轮区间为[i,right]
                left = i;
            }
        }
        int i = left;
        int j = totalNums - i;
        int leftNums1Max = i == 0? Integer.MIN_VALUE : nums1[i-1];
        int rightNums1Min = i == m? Integer.MAX_VALUE: nums1[i];
        int leftNums2Max = j == 0? Integer.MIN_VALUE : nums2[j-1];
        int rightNums2Min = j == n? Integer.MAX_VALUE: nums2[j];
        if(((m+n))%2==1){
            //奇数,找左边
            return Math.max(leftNums1Max,leftNums2Max);
        }else{
            // 偶数,找左边最大,右边最小
            return (double)(Math.max(leftNums1Max,leftNums2Max) + Math.min(rightNums1Min,rightNums2Min))/2;
        }
    }

    public static void main(String[] args) {
        int nums1[] = {1,3};
        int nums2[] = {2,7};
        Code4 code4 = new Code4();
        System.out.println(code4.findMedianSortedArrays(nums1,nums2));
    }


}
